package com.yequan.leetcode.heap.maxSlidingWindow_239;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author yq
 * @date 2020/06/28
 */
public class RecodeMaxSlidingWindow {

    /**
     * 大顶堆法
     * 1.用大顶堆存储滑动窗口数据
     * 2.先移除滑动窗口第一个数据
     * 3.存入新的数据
     * 4.堆出队列，存入结果中
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>((n1, n2) -> n2 - n1);
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            int start = i - k;
            if (start >= 0) {
                heap.remove(nums[start]);
            }
            heap.offer(nums[i]);
            if (heap.size() == k) {
                res[i - k + 1] = heap.peek();
            }
        }
        return res;
    }

}
